package top.fengleifeng.question;

import top.fengleifeng.util.Constants;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: leetcode-test
 * @description:
 * @author: fengleifeng
 * @create: 2020-09-30 16:18
 **/
public class Num695岛屿的最大面积 {

    class Solution {
        public int maxAreaOfIsland(int[][] grid) {
            if (grid.length < 0) {
                return 0;
            }
            Constants.printArrs(grid);
            boolean[][] used = new boolean[grid.length][grid[0].length];
            int max = 0;
            //遍历每个旗子
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    //没访问过 并且是陆地
                    if (!used[i][j] && grid[i][j] == 1) {
                        used[i][j] = true;
                        int num = bfs(grid, used, i, j, 0);
                        max = Math.max(num, max);
                    }
                }
            }
            return max;
        }

        private int bfs(int[][] grid, boolean[][] used, int ii, int jj, int num) {
            Queue<int[]> queue = new LinkedList();
            queue.add(new int[]{ii, jj});
            while (!queue.isEmpty()) {
                int[] poll = queue.poll();
                int i = poll[0];
                int j = poll[1];
                //上下左右
                num++;
                if (i - 1 >= 0 && !used[i - 1][j] && grid[i - 1][j] == 1) {
                    used[i - 1][j] = true;
                    queue.add(new int[]{i - 1, j});
                }
                if (i + 1 < grid.length && !used[i + 1][j] && grid[i + 1][j] == 1) {
                    used[i + 1][j] = true;
                    queue.add(new int[]{i + 1, j});
                }
                if (j + 1 < grid[i].length && !used[i][j + 1] && grid[i][j + 1] == 1) {
                    used[i][j + 1] = true;
                    queue.add(new int[]{i, j + 1});
                }
                if (j - 1 >= 0 && !used[i][j - 1] && grid[i][j - 1] == 1) {
                    used[i][j - 1] = true;
                    queue.add(new int[]{i, j - 1});
                }
            }
            return num;
        }
    }

    public static void main(String[] args) {
        int[][] ints = {{1, 1, 0, 0, 0}, {1, 1, 0, 0, 0}, {0, 0, 0, 1, 1}, {0, 0, 0, 1, 1}};
        int i = new Num695岛屿的最大面积().new Solution().maxAreaOfIsland(ints);
        System.out.println(i);
    }
}
